package com.lx.algorithm.manacher;

import static com.lx.algorithm.kmp.Kmp.getRandomString;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-14 10:23:03
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-14     张李鑫                     1.0         1.0 Version
 */
public class Manacher {

    /**
     * Manacher 找最长回文子串
     */

    public static int manacher(String str) {
        if (str == null) {
            return -1;
        }
        String manacherStr = manacherStr(str.toCharArray());
        int[] manacherArr = new int[manacherStr.length()];
        //最右边的边界在哪里
        int r = -1;
        //边界的半径在哪里
        int c = -1;
        int max = 1;
        char[] chars = manacherStr.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            //如果i被r包裹在范围内 他们的回文半径 最短 是对称的i' 的长度 c-（i-c） 所以是2c-i
            // 如果i'在边界外 所以可能会大于r-i 先取r-i 后面通过循环去增
            manacherArr[i] = r > i ? Math.min(manacherArr[2 * c - i], r - i) : 1;
            while (i + manacherArr[i] < chars.length && i - manacherArr[i] > -1) {
                //没有超过左右半径的长度 回文半径++
                if (chars[i + manacherArr[i]] == chars[i - manacherArr[i]]) {
                    manacherArr[i]++;
                } else {
                    break;
                }
            }
            if (i + manacherArr[i] > r) {
                r = i + manacherArr[i];
                c = i;
            }
            max = Math.max(max, manacherArr[i]);
        }
        return max - 1;
    }

    public static int right(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = manacherStr(s.toCharArray()).toCharArray();
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            int L = i - 1;
            int R = i + 1;
            while (L >= 0 && R < str.length && str[L] == str[R]) {
                L--;
                R++;
            }
            max = Math.max(max, R - L - 1);
        }
        return max / 2;
    }

    private static String manacherStr(char[] str) {
        StringBuilder stringBuilder = new StringBuilder();
        for (char c : str) {
            stringBuilder.append("#").append(c);
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            if (manacher(str) != right(str)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }


}

